package algorithm.string;

/**
 * leetcode : https://leetcode.com/problems/longest-common-prefix/description/
 * Difficulty : Easy
 *
 * 字符串集合内最长前缀
 * 难点在于边界值的各种判断
 *
 * 还有一个思路：
 * https://leetcode.com/problems/longest-common-prefix/discuss/153447/Another-Java-solution.-It-beats-100-:)
 *
 * @Author Antony
 * @Since 2018/7/26 20:04
 */
public class LongestCommonPrefix {


    /**
     * beats 100% - 5ms
     */
    public String longestCommonPrefix_other(String[] strs) {
        if (strs.length==0) {
            return "";
        }
        String pre = strs[0];
        for(String s:strs) {
            if (!s.startsWith(pre)) {
                int length = Math.min(s.length(), pre.length());
                StringBuilder sb = new StringBuilder();
                for (int i=0; i<length; i++) {
                    if (pre.charAt(i)==s.charAt(i)){
                        sb.append(s.charAt(i));
                    } else {
                        break;
                    }
                }
                pre = sb.toString();
                if (pre.length()==0){
                    return "";
                }
            }
        }
        return pre;
    }


    /**
     * beats 41.3% - 7ms
     *
     * 逐个比较字符
     * 还是不够快
     */
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) return "";
        if(strs.length == 1) return strs[0];
        int lastIndex = 0;
        String tmpStr = strs[0];
        while(lastIndex < tmpStr.length()){
            char tmp = strs[0].charAt(lastIndex);
            for(int i=1; i<strs.length; i++){
                if(lastIndex >= strs[i].length() || tmp != strs[i].charAt(lastIndex)){
                    return lastIndex>0 ? strs[0].substring(0,lastIndex) : "";
                }
            }
            lastIndex++;
        }
        return tmpStr;
    }
}
